Scheduling a divisible task in a two-dimensional toroidal mesh
Identifieur interne : 001123 ( France/Analysis ); précédent : 001122; suivant : 001124Scheduling a divisible task in a two-dimensional toroidal mesh
Auteurs : Jacek Bła Ewicz [Pologne] ; Maciej Drozdowski [Pologne] ; Frédéric Guinand [France] ; Denis Trystram [France]Source :
- Discrete Applied Mathematics [ 0166-218X ] ; 1999.
Abstract
In this paper, a problem of scheduling an arbitrarily divisible task is considered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes total execution time. We focus on two dimensional processor networks assuming a circuit-switching routing mechanism. The scheduling method uses a scattering scheme proposed in Peters and Syska (IEEE Trans. Parallel Distributed Systems 7(3) (1996) 246–255) to distribute parts of the task to processors in a minimum time. We show how to model and solve this problem with a set of algebraic equations. A solution of the latter allows one to analyze the performance of the network depending on various actual parameters of the task and the parallel machine. Though the method is defined for a particular architecture and scattering scheme it can be generalized to analyze other architectures of parallel computer systems.
Url:
DOI: 10.1016/S0166-218X(99)00013-X
Affiliations:
- France, Pologne
- Auvergne-Rhône-Alpes, Haute-Normandie, Rhône-Alpes, Région Normandie
- Grenoble, Le Havre
- Université du Havre
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001322
- to stream Istex, to step Curation: 001322
- to stream Istex, to step Checkpoint: 000A24
- to stream Main, to step Merge: 001A64
- to stream Main, to step Curation: 001A15
- to stream Main, to step Exploration: 001A15
- to stream France, to step Extraction: 001123
Links to Exploration step
ISTEX:029E9058119807B4048657E19139884D96FB7674Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Scheduling a divisible task in a two-dimensional toroidal mesh</title><author><name sortKey="Bla Ewicz, Jacek" sort="Bla Ewicz, Jacek" uniqKey="Bla Ewicz J" first="Jacek" last="Bła Ewicz">Jacek Bła Ewicz</name></author><author><name sortKey="Drozdowski, Maciej" sort="Drozdowski, Maciej" uniqKey="Drozdowski M" first="Maciej" last="Drozdowski">Maciej Drozdowski</name></author><author><name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name></author><author><name sortKey="Trystram, Denis" sort="Trystram, Denis" uniqKey="Trystram D" first="Denis" last="Trystram">Denis Trystram</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:029E9058119807B4048657E19139884D96FB7674</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0166-218X(99)00013-X</idno><idno type="url">https://api.istex.fr/document/029E9058119807B4048657E19139884D96FB7674/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001322</idno><idno type="wicri:Area/Istex/Curation">001322</idno><idno type="wicri:Area/Istex/Checkpoint">000A24</idno><idno type="wicri:doubleKey">0166-218X:1999:Bla Ewicz J:scheduling:a:divisible</idno><idno type="wicri:Area/Main/Merge">001A64</idno><idno type="wicri:Area/Main/Curation">001A15</idno><idno type="wicri:Area/Main/Exploration">001A15</idno><idno type="wicri:Area/France/Extraction">001123</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Scheduling a divisible task in a two-dimensional toroidal mesh</title><author><name sortKey="Bla Ewicz, Jacek" sort="Bla Ewicz, Jacek" uniqKey="Bla Ewicz J" first="Jacek" last="Bła Ewicz">Jacek Bła Ewicz</name><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 3a. 60-965 Poznań</wicri:regionArea><wicri:noRegion>ul. Piotrowo 3a. 60-965 Poznań</wicri:noRegion></affiliation></author><author><name sortKey="Drozdowski, Maciej" sort="Drozdowski, Maciej" uniqKey="Drozdowski M" first="Maciej" last="Drozdowski">Maciej Drozdowski</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 3a. 60-965 Poznań</wicri:regionArea><wicri:noRegion>ul. Piotrowo 3a. 60-965 Poznań</wicri:noRegion></affiliation></author><author><name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d'Informatique du Havre, Universite du Havre, BP 540, 25, Rue Philippe Lebon. 76058 Le Havre Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region><settlement type="city">Le Havre</settlement></placeName><orgName type="university">Université du Havre</orgName></affiliation></author><author><name sortKey="Trystram, Denis" sort="Trystram, Denis" uniqKey="Trystram D" first="Denis" last="Trystram">Denis Trystram</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Modélisation et de Calcul, Institut Fourier, BP 53X, 100, Rue des Mathématiques, 38041 Grenoble Cedex 9</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Grenoble</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="ISSN">0166-218X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">94</biblScope><biblScope unit="issue">1–3</biblScope><biblScope unit="page" from="35">35</biblScope><biblScope unit="page" to="50">50</biblScope></imprint><idno type="ISSN">0166-218X</idno></series><idno type="istex">029E9058119807B4048657E19139884D96FB7674</idno><idno type="DOI">10.1016/S0166-218X(99)00013-X</idno><idno type="PII">S0166-218X(99)00013-X</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0166-218X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper, a problem of scheduling an arbitrarily divisible task is considered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes total execution time. We focus on two dimensional processor networks assuming a circuit-switching routing mechanism. The scheduling method uses a scattering scheme proposed in Peters and Syska (IEEE Trans. Parallel Distributed Systems 7(3) (1996) 246–255) to distribute parts of the task to processors in a minimum time. We show how to model and solve this problem with a set of algebraic equations. A solution of the latter allows one to analyze the performance of the network depending on various actual parameters of the task and the parallel machine. Though the method is defined for a particular architecture and scattering scheme it can be generalized to analyze other architectures of parallel computer systems.</div></front></TEI><affiliations><list><country><li>France</li><li>Pologne</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Haute-Normandie</li><li>Rhône-Alpes</li><li>Région Normandie</li></region><settlement><li>Grenoble</li><li>Le Havre</li></settlement><orgName><li>Université du Havre</li></orgName></list><tree><country name="Pologne"><noRegion><name sortKey="Bla Ewicz, Jacek" sort="Bla Ewicz, Jacek" uniqKey="Bla Ewicz J" first="Jacek" last="Bła Ewicz">Jacek Bła Ewicz</name></noRegion><name sortKey="Bla Ewicz, Jacek" sort="Bla Ewicz, Jacek" uniqKey="Bla Ewicz J" first="Jacek" last="Bła Ewicz">Jacek Bła Ewicz</name><name sortKey="Drozdowski, Maciej" sort="Drozdowski, Maciej" uniqKey="Drozdowski M" first="Maciej" last="Drozdowski">Maciej Drozdowski</name></country><country name="France"><region name="Région Normandie"><name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name></region><name sortKey="Trystram, Denis" sort="Trystram, Denis" uniqKey="Trystram D" first="Denis" last="Trystram">Denis Trystram</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001123 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 001123 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= France
|étape= Analysis
|type= RBID
|clé= ISTEX:029E9058119807B4048657E19139884D96FB7674
|texte= Scheduling a divisible task in a two-dimensional toroidal mesh
}}
| This area was generated with Dilib version V0.6.25. |  |